/**
 * 
 */
package linkedlist.passed;

import linkedlist.Node;
import utils.CreateUtils;
import utils.PrintUtils;

/**
 * @author xyyi
 * @param <E>
 *
 */
public class MergeSortForLinkedList {

	public static <E extends Comparable<? super E>> Node<E> mergeSort(
			Node<E> head) {
		int length = 0;
		Node<E> curr = head;
		while (curr != null) {
			length++;
			curr = curr.next;
		}

		return mergeSort(head, length);
	}

	public static <E extends Comparable<? super E>> Node<E> mergeSort(
			Node<E> head, int length) {
		if (head == null || length == 1) {
			return head;
		}

		Node<E> secondHead = head;
		int fisrtLength = length / 2;
		for (int i = 0, len = fisrtLength - 1; i < len; i++) {
			secondHead = secondHead.next;
		}
		Node<E> next = secondHead.next;
		secondHead.next = null;
		secondHead = next;

		head = mergeSort(head, fisrtLength);
		secondHead = mergeSort(secondHead, length - fisrtLength);

		head = merge(head, secondHead);
		return head;
	}

	public static <E extends Comparable<? super E>> Node<E> merge(
			Node<E> head1, Node<E> head2) {
		if (head1 == null && head2 == null) {
			return null;
		}
		if (head1 == null) {
			return head2;
		}
		if (head2 == null) {
			return head1;
		}

		Node<E> head = new Node<E>();
		Node<E> curr1 = head1, curr2 = head2, curr = head;
		while (curr1 != null && curr2 != null) {
			if (curr1.compareTo(curr2) <= 0) {
				curr.next = curr1;
				curr1 = curr1.next;
			} else {
				curr.next = curr2;
				curr2 = curr2.next;
			}
			curr = curr.next;
		}

		if (curr1 != null) {
			curr.next = curr1;
		} else if (curr2 != null) {
			curr.next = curr2;
		}

		return head.next;
	}

	/**
	 * 
	 */
	public MergeSortForLinkedList() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//		Node<Integer> head = new Node<Integer>(7), curr = head;
		//		curr.next = new Node<Integer>(8);
		//		curr = curr.next;
		//		curr.next = new Node<Integer>(8);
		//		curr = curr.next;
		//		curr.next = new Node<Integer>(3);
		//		curr = curr.next;
		//		curr.next = new Node<Integer>(9);
		//		curr = curr.next;
		//		curr.next = new Node<Integer>(3);
		//		curr = curr.next;
		//		curr.next = new Node<Integer>(9);
		//		curr = curr.next;
		//		curr.next = new Node<Integer>(5);
		//		curr = curr.next;
		//		PrintUtils.printLinkedList(head);
		//		System.out.println();
		//		PrintUtils.printLinkedList(MergeSortForLinkedList.mergeSort(head));

		Node<Integer> head = CreateUtils.randNonNegLinkedList(10, 10);
		PrintUtils.printLinkedList(head);
		System.out.println();
		PrintUtils.printLinkedList(MergeSortForLinkedList.mergeSort(head));
	}
}
